package 图.最小生成树;

import 抽象数据类型.Edge;
import 抽象数据类型.EdgeWeightedGraph;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-11
 */
public class 最小生成树Prim算法的延时实现 {
    public static void main(String[] args) {
        int[] arr1 = {0, 1, 0, 1, 1, 4, 2, 1};
        int[] arr2 = {1, 2, 2, 4, 3, 3, 3, 3};
        double[] weight = {1, 2, 3, 2, 3, 3, 2, 3};
        EdgeWeightedGraph G = new EdgeWeightedGraph(arr1.length);
        G.addGraph(arr1, arr2, weight);
        LazyPrimMST dijkstraSP = new LazyPrimMST(G);
        for (Edge edge : dijkstraSP.edges()) {
            System.out.println(edge);
        }

    }
    public static class LazyPrimMST {
        private boolean[] marked;
        private Queue<Edge> mst;
        private PriorityQueue<Edge> pq;

        public LazyPrimMST(EdgeWeightedGraph g) {
            pq = new PriorityQueue<>((o1, o2) -> o1.compareTo(o2));
            marked = new boolean[g.V()];
            mst = new LinkedList();
            visit(g, 0);
            while (!pq.isEmpty()) {
                Edge e = pq.poll();
                int v = e.either();
                int w = e.other(v);
                if (marked[v] && marked[w]) {
                    continue;
                }
                mst.offer(e);
                if (!marked[v]) {
                    visit(g, v);
                }
                if (!marked[w]) {
                    visit(g, w);
                }

            }
        }

        private void visit(EdgeWeightedGraph g, int v) {
            marked[v] = true;
            for (Edge e : g.adj(v)) {
                if (!marked[e.other(v)]) {
                    pq.offer(e);
                }
            }
        }

        public Iterable<Edge> edges() {
            return this.mst;
        }
    }
}
